/**
 * 301. 删除无效的括号
 * https://leetcode-cn.com/problems/remove-invalid-parentheses/
 */
const { displayBaseArray } = require('../../libs/public');

const leftPCode = '('.charCodeAt(0);
const rightPCode = ')'.charCodeAt(0);

let stack;
let top = -1;
let bottom = 0;

/**
 * @param {number} value
 */
function pushStack(value) {
  top += 1;
  stack[top] = value;
}

/**
 * @return {number}
 */
function popStack() {
  top -= 1;
  return stack[top + 1];
}

/**
 * @return {number}
 */
function stackTop() {
  return top >= 0 ? stack[top] : -1;
}

/**
 * @return {number}
 */
function stackLength() {
  return top - bottom + 1;
}

function clearStack() {
  top = -1;
  bottom = 0;
}

/**
 * @param {string} s
 * @return {boolean}
 */
function isSInvalid(s) {
  clearStack();
  for (let i = 0; i < s.length; i += 1) {
    const code = s.charCodeAt(i);
    if (code === leftPCode) {
      pushStack(code);
    } else if (code === rightPCode) {
      if (stackTop() === leftPCode) {
        popStack();
      } else {
        return false;
      }
    }
  }
  return stackLength() <= 0;
}

let result;

/**
 * @param {string} s
 * @param {number} begin
 * @param {number} count
 */
function deleteRightParentheses(s, begin, count) {
  if (!count) {
    if (isSInvalid(s)) {
      result.add(s);
    }
    return;
  }
  const first = s.indexOf(')', begin);
  if (first < 0) {
    return;
  }
  deleteRightParentheses(s, first + 1, count);
  s = s.substring(0, first) + s.substring(first + 1);
  deleteRightParentheses(s, first, count - 1);
}

/**
 * @param {string} s
 * @param {number} begin
 * @param {number} count
 * @param {number} rightCount
 */
function deleteLeftParentheses(s, begin, count, rightCount) {
  if (!count) {
    deleteRightParentheses(s, 0, rightCount);
    return;
  }
  const first = s.indexOf('(', begin);
  if (first < 0) {
    return;
  }
  deleteLeftParentheses(s, first + 1, count, rightCount);
  s = s.substring(0, first) + s.substring(first + 1);
  deleteLeftParentheses(s, first, count - 1, rightCount);
}

/**
 * @param {string} s
 * @return {string[]}
 */
function removeInvalidParentheses(s) {
  stack = new Array(s.length).fill(0);
  let rightPToDelete = 0;
  for (let i = 0; i < s.length; i += 1) {
    const code = s.charCodeAt(i);
    if (code === leftPCode) {
      if (stackTop() === rightPCode) {
        rightPToDelete += stackLength();
        clearStack();
      }
      pushStack(code);
    } else if (code === rightPCode) {
      if (stackTop() === leftPCode) {
        popStack();
      } else {
        pushStack(code);
      }
    }
  }
  let leftPToDelete = 0;
  if (stackTop() === leftPCode) {
    leftPToDelete = stackLength();
  } else if (stackTop() === rightPCode) {
    rightPToDelete += stackLength();
  }
  result = new Set();
  deleteLeftParentheses(s, 0, leftPToDelete, rightPToDelete);
  return Array.from(result);
}

console.log(displayBaseArray(removeInvalidParentheses('()())()')) === '[()()(),(())()]');
console.log(displayBaseArray(removeInvalidParentheses('(a)())()')) === '[(a)()(),(a())()]');
console.log(displayBaseArray(removeInvalidParentheses(')(')) === '[]');
console.log(displayBaseArray(removeInvalidParentheses('((')) === '[]');
console.log(displayBaseArray(removeInvalidParentheses('))')) === '[]');
